Many methods have been developed in two-dimensional (2D) computer graphics in recent times to improve the quality of output. Rendering of graphical objects that have a solid color or a linear or radial blend between two colors has also been performed for many years. More recently methods such as Gouraud shaded triangle meshes and blends across parametric patches have been adapted from three-dimensional (3D) computer graphics to 2D computer graphics in order to greatly increase the shapes and styles of blends that may be produced.
A geometric object referred to herein as a parametric patch may be defined by four curves (e.g., Bézier curves) in xy coordinate space. The four curves typically map a unit square in parametric uv coordinate space. Examples of such parametric patches are Coons and tensor-product patches. A Coons patch may be defined by four connected Bézier Curves and four implicit control points. Portable Document Format (PDF) “Type 6” shading performed in accordance with the Portable Document Format (PDF) ISO32000-1:2008 specification comprises one or more colored Coons patches. Such shading will be referred to below as “PDF type 6 shading”. A tensor-product patch may be defined by four connected Bézier Curves and by additional control points.
PDF “Type 7” shading performed in accordance with the PDF ISO32000-1:2008 standard comprises one or more colored tensor-product patches. Such shading will be referred to below as “PDF type 7 shading”. The Coons patch determined as part of the PDF type 6 shading is a special case of a tensor-product patch. Coons patches may be converted to tensor-product patches.
Each point in a PDF type 6 or type 7 shading patch may be associated with a t-value which is mapped to a color value using a PDF shading color function. The PDF shading color function may be non-linear. In PDF type 6 or type 7 shading, the color data of each of the four corners of the parametric patch may be specified by t-values.
Vector graphics on imaging devices, such as display devices or printers, are typically converted to raster graphics data in a process called rasterization. During rasterization, surfaces defined by geometric objects may be subdivided into polygons (e.g. triangles or quadrilaterals) in a process called tessellation.
Methods are known for tessellating parametric patches from PDF type 6 and 7 shadings into triangle meshes using recursive subdivision, such as “De-Casteljau's method”. Recursive methods are not amenable to all implementation platforms. Embedded systems, for instance, have limited stack space and so cannot afford deep levels of recursion.
One known method of rendering parametric patches is to map each pixel in the xy space that belongs to a patch back to a corresponding point(s) in the uv parametric space. The mapping typically involves inverting patch parametric equations. Once the corresponding point(s) in the uv parametric space is known, the color associated with the corresponding point(s) is determined and applied to an original pixel at that corresponding point(s) in the xy space. While such rendering methods provide high quality output, such methods are not always the most efficient as the methods operate per-pixel. Further, such rendering methods may not take advantage of specific hardware acceleration such as three (3) point blend hardware support.
Another known method of tessellating parametric patches from PDF type 6 and 7 shadings using a predetermined tessellation depth is also known. However, the quality of the output from the predetermined tessellation depth methods is not acceptable when rendering some PDF type 6 and 7 shadings which use PDF shading color functions. Moreover, the performance of the predetermined tessellation depth methods is impacted by multiple tessellation stages, one stage for tessellating the patch into triangles and another stage for recursively tessellating the triangles into smaller triangles.
Methods are known for tessellating shading triangles further into triangle meshes using recursive subdivision in which middle points of edges of a triangle are computed and then four triangles are constructed by joining the middle points. The subdivision process is recursively invoked for resulting triangles, where the recursion process stops when the colors of vertices of the triangle differ within a certain tolerance. Recursive methods of tessellating shading triangles are not amenable to all implementation platforms. Embedded systems, for instance, have limited stack space and so cannot afford deep levels of recursion. Also, such recursive methods of tessellating shading triangles do not cater for the non-linearity in the PDF shading color function.
Thus, a need clearly exists for a more efficient method of rendering shading objects from PDF type 6 and 7 shadings, which improves computer graphics output quality.